// 21. 合并两个有序链表
// 链表

// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

// 输入：l1 = [1,2,4], l2 = [1,3,4]
// 输出：[1,1,2,3,4,4]
// 示例 2：

// 输入：l1 = [], l2 = []
// 输出：[]
// 示例 3：

// 输入：l1 = [], l2 = [0]
// 输出：[0]

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
let l1 = {
	val: 1,
	next: {
		val: 2,
		next: {
			val: 4,
			next: null,
		},
	},
}
let l2 = {
	val: 1,
	next: {
		val: 3,
		next: {
			val: 4,
			next: null,
		},
	},
}
function ListNode(val, next) {
	this.val = val === undefined ? 0 : val
	this.next = next === undefined ? null : next
}

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 * @description 递归
 */

var mergeTwoLists1 = function (l1, l2) {
	if (l1 === null) {
		return l2
	} else if (l2 === null) {
		return l1
	} else if (l1.val <= l2.val) {
		l1.next = mergeTwoLists(l1.next, l2)
		return l1
	} else {
		l2.next = mergeTwoLists(l1, l2.next)
		return l2
	}
}

// console.log('[ mergeTwoLists1(l1,l2) ] >', mergeTwoLists1(l1, l2))

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 * @description 迭代
 */

var mergeTwoLists2 = function (l1, l2) {
	const head = new ListNode(-1)
	let cur = head
	while (l1 != null && l2 != null) {
		if (l1.val <= l2.val) {
			cur.next = l1
			l1 = l1.next
		} else {
			cur.next = l2
			l2 = l2.next
		}
		cur = cur.next
	}
	cur.next = l1 === null ? l2 : l1
	return head.next
}

console.log('[ mergeTwoLists2(l1,l2) ] >', mergeTwoLists2(l1, l2))
